1049. Last Stone Weight II

#Algorithm #Algorithm_Knapsack

1049. Last Stone Weight II

1. 문제

1-1. 원문

You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose any two stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.

Example 1:
Input: stones = [2,7,4,1,8,1]
Output: 1
Explanation:
We can combine 2 and 4 to get 2, so the array converts to [2,7,1,8,1] then,
we can combine 7 and 8 to get 1, so the array converts to [2,1,1,1] then,
we can combine 2 and 1 to get 1, so the array converts to [1,1,1] then,
we can combine 1 and 1 to get 0, so the array converts to [1], then that's the optimal value.

Example 2:
Input: stones = [31,26,33,21,40]
Output: 5

Constraints:

1-2. 내용 번역

stones 배열이 주어지는데, stones[i]는 i번 인덱스에 있는 돌의 무게이다.
이 돌들을 가지고 게임을 한다. 각 턴에서 두 개의 돌을 맞부딪친다. 두 개의 돌을 각각 x와 y라고 하고 무게는 x <= y 라고 할 때, 게임의 결과는 다음과 같다.

2. 문제 이해

2-1. 내용 이해

Example1을 가지고 이해해보자.
각 돌들의 무게가 2, 7, 4, 1, 8, 1 이다.
2와 7을 부딪치면 무게2짜리 돌은 사라지고 7짜리 돌은 무게 5를 가진 돌이 된다. 남은 무게 5짜리 돌과 그 다음 돌인 무게 4짜리 돌을 부딪치면 무게 5짜리 돌은 무게 1짜리 돌이 되고, 무게 4짜리 돌은 사라진다. 이런식으로 돌을 맞부딪치는 게임이다. 이렇게 배열 인덱스 순서대로(2 -> 7 -> 4 -> 1 -> 8 -> 1) 진행하게 되면 남는 돌의 무게는 7이 된다.
하지만 2 -> 4 -> 1 -> 1 -> 7 -> 8 순으로 진행하게 되면 남는 돌의 무게는 1이 된다. 어떤 경우도 이 돌들을 가지고 남길 수 있는 가장 최소의 무게는 1이기 때문에 답은 1이 된다.

2-2. 접근법 생각

Knapsack문제만 골라서 풀기 위해 검색해서 찾은 문제이기 때문에 Knapsack으로 풀이법을 구상해보려고 노력했다. 때문에 이 문제를 모든 알고리즘을 대상으로 열어두고 풀이법을 고민해봤을때 Knapsack이 생각이 날 수 있는지는 아직 잘 모르겠다.
얼핏보면 knapsack 알고리즘의 요소들이 잘 보이지 않기 때문인데, 생각을 잠시 하고 난 뒤에는 요소를 독특하게 구성했다는 느낌이 들었다. 보통은 가방의 무게가 주어지거나 적어도 물건의 무게와 가방의 무게는 다른 대상으로 지정되는데 여기서는 돌의 무게를 가방의 무게로 둘 수도 있고 물건의 무게로 둘 수도 있다고 생각해야 knapsack을 구성할 수 있다. 또한 물건의 가치는 돌의 무게가 아니라 가방의 무게와 돌의 무게의 차이이고 가장 적은 가치를 가질 수 있도록 만들어야 한다. 한가지 더 생각하자면 배낭의 무게와 돌의 무게는 뒤바뀔 수도 있다. 그러니까 배낭의 무게가 마이너스가 되어버리면 즉시 돌의 무게와 배낭의 무게가 바뀌어서 배낭의 무게는 항상 양의 값으로 유지시킬 수 있는 것이다.

2-3. 적용한 풀이

Knapsack BottomUp (Tabulation)

배낭 알고리즘 문제를 만나게 되면 처음에는 재귀의 형태로 생각하면서 수학적 귀납법의 식을 만들어내게 되는데, 이것을 계속 전개시키다보면 어느순간 tabulation으로도 생각할 수 있게 된다.
(+ knapsack을 이번에 다시 공부할 때에는 tabulation이 사고에 역행하는 방식이라고 생각되어서 자연적이지 않은 풀이법이라는 생각이 들었는데, knapsack에 익숙해질 수록 tabulation으로 풀게되면서 생각이란건 하면 할 수록 형식을 뛰어넘는구나 라는 생각이 들게된다.)

3. 구현

class Solution {
    fun lastStoneWeightII(stones: IntArray): Int {
        var total = 0

        for (stone in stones) {
            total += stone
        }

		// 배열의 구성은 i번째 돌*배낭의 무게=i번째 돌을 생각할 때 해당 배낭의 무게로 만들 수 있는지의 여부
        val memo = Array(stones.size){Array(total+1){false}}
        
        memo[0][stones[0]] = true

        for(idx in 1..stones.size-1) {
            for(curTotal in 0..total) {
                if (memo[idx-1][curTotal] == true) {
	                // 이번 돌의 무게가 돌의 무게로서 다뤄지는 경우
                    val diffAbs = Math.abs(curTotal-stones[idx])
                    // 이번 돌의 무게가 배낭의 무게로 추가되는 경우
                    val sum = stones[idx]+curTotal

                    memo[idx][diffAbs] = true
                    memo[idx][sum] = true
                }
            }
        }

		// 마지막 돌에서 만들 수 있는 가장 작은 무게가 얼마인지를 오름차순으로 체크하면서 골라냄
        for (total in 0..total) {
            if (memo[stones.size-1][total]) {
                return total
            }
        }

        return -1
    }
}

4. 복잡도